#include<string>
#include<vector>
#include<iostream>
using std::string;
using std::vector;


class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {};
        vector<string> res = {};
        this->generate(res, "", n, n);
        return res;
    }

    void generate(vector<string>& parenthesis, string curStr, int left, int right) {
        //std::cout << left << " " << right << "\n";
        if (left == 0 && right == 0) {
            parenthesis.push_back(curStr);
            return;
        }
        if (left < 0 || right < 0) return;
        if (left <= right) this->generate(parenthesis, curStr+'(', left-1, right);
        if (right > left) this->generate(parenthesis, curStr+')', left, right-1);
        
        return;

    }
};


int main() {
    auto res = Solution().generateParenthesis(3);
    for (auto s: res) std::cout << s << "\n";
}